﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Platform.Linq
{
	/// <summary>
	/// 
	/// </summary>
	/// <typeparam name="TNode"></typeparam>
	public class TreeQuery<TNode> : IEnumerable<TNode>
	{
		private Func<TNode, IEnumerable<TNode>> getBranch;

		/// <summary>
		/// 
		/// </summary>
		/// <param name="root"></param>
		/// <param name="getBranch"></param>
		public TreeQuery( TNode root, Func<TNode, IEnumerable<TNode>> getBranch )
			: this( new TNode[] { root }, getBranch )
		{ }

		/// <summary>
		/// 
		/// </summary>
		/// <param name="nodes"></param>
		/// <param name="getBranch"></param>
		public TreeQuery( IEnumerable<TNode> nodes, Func<TNode, IEnumerable<TNode>> getBranch )
		{
			this.Nodes = nodes;
			this.getBranch = getBranch;
		}

		/// <summary>
		/// 
		/// </summary>
		public IEnumerable<TNode> Nodes
		{ get; private set; }

		/// <summary>
		/// 
		/// </summary>
		public Func<TNode, IEnumerable<TNode>> GetBranch
		{ get { return this.getBranch; } }

		/// <summary>
		/// 
		/// </summary>
		public Func<TreeNodeCursor<TNode>, TreeQueryResult> Condition
		{ get; private set; }


		public void MatchIfTrue( Func<TreeNodeCursor<TNode>, bool> cond )
		{
			this.MatchIfTrue( cond, TreeQueryResult.NotMatched );
		}

		public void MatchIfTrue( Func<TreeNodeCursor<TNode>, bool> cond, TreeQueryResult notMatched )
		{
			this.Match( cursor => cond( cursor ) ? TreeQueryResult.Matched : notMatched );
		}

		public void Match( Func<TreeNodeCursor<TNode>, TreeQueryResult> condition )
		{
			if ( this.Condition == null )
			{
				this.Condition = condition;
			}
			else
			{
				var current = this.Condition;

				this.Condition =
					cursor =>
					{
						var result = current( cursor );

						if ( result == TreeQueryResult.NotInThisBranch
							|| result == TreeQueryResult.StopSearching )
						{
							return result;
						}
						else
						{
							return condition( cursor );
						}
					};
			}
		}

		public TreeQuery<T> OfType<T>()
			where T : TNode
		{
			this.MatchIfTrue( cursor => cursor.Current is T );
			return new TreeQuery<T>( this.OfType<T>(), x => this.getBranch( x ).OfType<T>() );
		}

		/// <summary>
		/// 
		/// </summary>
		/// <param name="condition"></param>
		/// <returns></returns>
		protected IEnumerable<TNode> DoSearch( Func<TreeNodeCursor<TNode>, TreeQueryResult> condition )
		{
			Queue<TreeNodeCursor<TNode>> nodes = new Queue<TreeNodeCursor<TNode>>();

			int nodeIndex = 0;
			foreach ( var node in this.Nodes )
			{
				nodes.Enqueue( new TreeNodeCursor<TNode>( node, nodeIndex++, this.Nodes, this.getBranch( node ) ) );
			}

			while ( nodes.Count > 0 )
			{
				var cCursor = nodes.Dequeue();	// Percorre cada nodo da árvore

				// Verifica se esse nodo satisfaz as condições
				TreeQueryResult conditionResult = condition( cCursor );

				// Achou o nodo
				if ( conditionResult == TreeQueryResult.Matched )
				{
					yield return cCursor.Current;
				}

				// Continua procurando nos nodos que restaram
				if ( conditionResult != TreeQueryResult.NotInThisBranch
					&& conditionResult != TreeQueryResult.StopSearching )
				{
					// Continua percorrendo a árvore de nodos
					TNode current = default( TNode );
					TNode last = default( TNode );
					nodeIndex = -1;

					// Adiciona todos os nodos, mas sempre adicionando o nodo anterior para 
					// ter acesso ao próximo nodo
					foreach ( var item in cCursor.Children )
					{
						if ( nodeIndex >= 0 )
						{
							nodes.Enqueue( new TreeNodeCursor<TNode>( last, current, item, nodeIndex, cCursor, this.getBranch( current ) ) );
						}

						last = current;
						current = item;
						nodeIndex++;
					}

					// Adiciona o último nodo 
					if ( nodeIndex >= 0 )
					{
						nodes.Enqueue( new TreeNodeCursor<TNode>( last, current, default( TNode ), nodeIndex, cCursor, this.getBranch( current ) ) );
					}
				}
			}
		}

		#region IEnumerable<TNode> Members

		public IEnumerator<TNode> GetEnumerator()
		{
			return this.DoSearch( this.Condition ).GetEnumerator();
		}

		#endregion

		#region IEnumerable Members

		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
		{
			return this.GetEnumerator();
		}

		#endregion
	}


	/// <summary>
	/// Relaciona o para onde ir
	/// </summary>
	public enum TreeQueryResult
	{
		/// <summary>
		/// 
		/// </summary>
		Matched = 0,

		/// <summary>
		/// 
		/// </summary>
		NotMatched = 1,

		/// <summary>
		/// 
		/// </summary>
		NotInThisBranch = 2,

		/// <summary>
		/// 
		/// </summary>
		StopSearching = 3
	}

	/// <summary>
	/// Identifica onde está o cursor 
	/// </summary>
	/// <typeparam name="TNode"></typeparam>
	public struct TreeNodeCursor<TNode>
	{
		public readonly TNode Parent;
		public readonly TNode Previous;
		public readonly TNode Current;
		public readonly TNode Next;

		public readonly IEnumerable<TNode> Siblings;
		public readonly IEnumerable<TNode> Children;

		public readonly int Level;
		public readonly int Index;

		public TreeNodeCursor( TNode root, int index, IEnumerable<TNode> siblings, IEnumerable<TNode> children )
		{
			this.Current = root;
			this.Previous
				= this.Next
				= this.Parent
				= default( TNode );

			this.Level = 0;
			this.Index = index;

			this.Siblings = siblings ?? Enumerable.Empty<TNode>();
			this.Children = children ?? Enumerable.Empty<TNode>();
		}

		public TreeNodeCursor( TNode previous, TNode current, TNode next, int index, TreeNodeCursor<TNode> parent, IEnumerable<TNode> children )
		{
			this.Previous = previous;
			this.Current = current;
			this.Next = next;
			this.Level = parent.Level + 1;
			this.Index = index;

			this.Parent = parent.Current;
			this.Children = children ?? Enumerable.Empty<TNode>();
			this.Siblings = parent.Children;
		}
	}

	/// <summary>
	/// 
	/// </summary>
	public static class QueryExtensionMethods
	{

		/// <summary>
		/// 
		/// </summary>
		/// <typeparam name="TNode"></typeparam>
		/// <param name="query"></param>
		/// <param name="condition"></param>
		/// <returns></returns>
		public static TreeQuery<TNode> LookingFor<TNode>( this TreeQuery<TNode> query, Func<TNode, bool> condition )
		{
			query.MatchIfTrue( cursor => condition( cursor.Current ) );
			return query;
		}

		/// <summary>
		/// 
		/// </summary>
		/// <typeparam name="TNode"></typeparam>
		/// <param name="query"></param>
		/// <param name="condition"></param>
		/// <returns></returns>
		public static TreeQuery<TNode> ParentOf<TNode>( this TreeQuery<TNode> query, Func<TNode, bool> condition )
		{
			query.MatchIfTrue( cursor => cursor.Children.Any( condition ) );
			return query;
		}

		/// <summary>
		/// 
		/// </summary>
		/// <typeparam name="TNode"></typeparam>
		/// <param name="query"></param>
		/// <param name="condition"></param>
		/// <returns></returns>
		public static TreeQuery<TNode> Has<TNode>( this TreeQuery<TNode> query, Func<TNode, bool> condition )
		{
			query.MatchIfTrue( cursor => new TreeQuery<TNode>( cursor.Children, query.GetBranch ).LookingFor( condition ).Any(), TreeQueryResult.NotInThisBranch );
			return query;
		}

		/// <summary>
		/// 
		/// </summary>
		/// <typeparam name="TNode"></typeparam>
		/// <param name="query"></param>
		/// <param name="condition"></param>
		/// <returns></returns>
		public static TreeQuery<TNode> Siblings<TNode>( this TreeQuery<TNode> query, Func<IEnumerable<TNode>, bool> condition )
		{
			query.MatchIfTrue( cursor => condition( cursor.Siblings ) );
			return query;
		}

		/// <summary>
		/// 
		/// </summary>
		/// <typeparam name="TNode"></typeparam>
		/// <param name="query"></param>
		/// <returns></returns>
		public static TreeQuery<TNode> IsLeaf<TNode>( this TreeQuery<TNode> query )
		{
			query.MatchIfTrue( cursor => !cursor.Children.Any() );
			return query;
		}

		public static TreeQuery<TNode> Alone<TNode>( this TreeQuery<TNode> query )
		{
			query.MatchIfTrue( cursor => cursor.Siblings.Count() == 1 );
			return query;
		}

		public static TreeQuery<TNode> AtLevel<TNode>( this TreeQuery<TNode> query, int level )
		{
			query.Match(
				cursor =>
				{
					if ( cursor.Level == level )
						return TreeQueryResult.Matched;
					else if ( cursor.Level < level )
						return TreeQueryResult.NotMatched;
					else //if ( cursor.Level > level )
						return TreeQueryResult.NotInThisBranch;
				} );
			return query;
		}
	}
}
